package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 力扣 572. 另一棵树的子树
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 *
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 * root 树上的节点数量范围是 [1, 2000]
 * subRoot 树上的节点数量范围是 [1, 1000]
 * -104 <= root.val <= 104
 * -104 <= subRoot.val <= 104
 *
 * @author HuWLin
 * */
public class SameRoot {
    List<Integer> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();
    int max,lNull,rNull;
    /*
    * @param root 被查找的树
    * @param subRoot 要查的树
    * */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        max = Integer.MIN_VALUE;
        //找出最大值，两棵树的最大值
        getMax(root);
        getMax(subRoot);
        //由于题目给的数据范围不大，不用考虑溢出问题
        lNull = max + 1;
        rNull = max + 1;
        //把树先序遍历，并且最后的左空姐点为lNull，右为rNull
        setList(root,list);
        setList(subRoot,subList);
        //用kmp进行比较
        return kmp();
    }
    private void getMax(TreeNode root) {
        if(root == null) return;
        max = Math.max(root.val,max);
        getMax(root.left);
        getMax(root.right);
    }
    private void setList(TreeNode root,List<Integer> l) {
        if(root == null) return;
        l.add(root.val);
        if(root.left != null) {
            setList(root.left,l);
        }else {
            l.add(lNull);
        }
        if(root.right != null) {
            setList(root.right,l);
        }else {
            l.add(rNull);
        }
    }
    //经典kmp算法
    private boolean kmp() {
        int listLen = list.size(),subLen = subList.size();
        //我这里dp存的是长度
        int[] dp = new int[subLen];
        for(int i = 1,j = 0;i < subLen;i ++) {
            while(j > 0 && !subList.get(i).equals(subList.get(j))) {
                j = dp[j - 1];
            }
            if(subList.get(i).equals(subList.get(j))) {
                j ++;
            }
            dp[i] = j;
        }
        for(int i = 0,j = 0;i < listLen;i ++) {
            while(j > 0 && !list.get(i).equals(subList.get(j))) {
                j = dp[j - 1];
            }
            if(list.get(i).equals(subList.get(j))) {
                j ++;
            }
            if(j == subLen) {
                return true;
            }
        }
        return false;
    }



    /*
    * 以下方式较简单不做解释
    * */
    public boolean isSubtree2(TreeNode root, TreeNode subRoot) {
        return dfs(root,subRoot);
    }
    private boolean dfs(TreeNode root,TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        return check(root,subRoot) || dfs(root.left,subRoot) || dfs(root.right,subRoot);
    }

    private boolean check(TreeNode root,TreeNode subRoot) {
        if(root == null && subRoot == null) {
            return true;
        }
        if(root == null || subRoot == null || root.val != subRoot.val) {
            return false;
        }

        return check(root.left,subRoot.left) && check(root.right,subRoot.right);
    }

}
